package uestc.lj.basicPromotion.dfs;

/**
 * 岛屿问题
 *
 * @Author:Crazlee
 * @Date:2021/11/25
 */
public class Code01_LandCounts {
	/**
	 * 一片区域中最多有多少岛屿
	 *
	 * @param m 初始区域数组
	 * @return 岛屿数量
	 */
	public static int landCounts(int[][] m) {
		if (m == null || m[0] == null) {
			return 0;
		}
		//行
		int N = m.length;
		//列
		int M = m[0].length;
		int res = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (m[i][j] == 1) {
					res++;
					process(m, i, j, N, M);
				}
			}
		}
		return res;
	}

	private static void process(int[][] m, int i, int j, int N, int M) {
		if (i < 0 || i >= N || j < 0 || j >= M || m[i][j] != 1) {
			return;
		}
		m[i][j] = 2;
		process(m, i - 1, j, N, M);
		process(m, i + 1, j, N, M);
		process(m, i, j - 1, N, M);
		process(m, i, j + 1, N, M);
	}

	public static void main(String[] args) {
		int[][] m1 = {{0, 0, 0, 0, 0, 0, 0, 0, 0},
				{0, 1, 1, 1, 0, 1, 1, 1, 0},
				{0, 1, 1, 1, 0, 0, 0, 1, 0},
				{0, 1, 1, 0, 0, 0, 0, 0, 0},
				{0, 0, 0, 0, 0, 1, 1, 0, 0},
				{0, 0, 0, 0, 1, 1, 1, 0, 0},
				{0, 0, 0, 0, 0, 0, 0, 0, 0},};
		System.out.println(landCounts(m1));

		int[][] m2 = {{0, 0, 0, 0, 0, 0, 0, 0, 0},
				{0, 1, 1, 1, 1, 1, 1, 1, 0},
				{0, 1, 1, 1, 0, 0, 0, 1, 0},
				{0, 1, 1, 0, 0, 0, 1, 1, 0},
				{0, 0, 0, 0, 0, 1, 1, 0, 0},
				{0, 0, 0, 0, 1, 1, 1, 0, 0},
				{0, 0, 0, 0, 0, 0, 0, 0, 0},};
		System.out.println(landCounts(m2));
	}
}
